package momo.multitree.util;

import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Vector;

import momo.multitree.structure.Edge;
import momo.multitree.structure.Graph;
import momo.multitree.structure.Node;
import momo.multitree.structure.Tree;

import junit.framework.TestCase;


public class CompactAlgoTest extends TestCase {

	protected void setUp() throws Exception {
		super.setUp();
	}

	protected void tearDown() throws Exception {
		super.tearDown();
	}
	
	public void testEnumerateAllSpanningTree()
	{
		Node node1 = new Node("1", 1, 1);
		Node node2 = new Node("2", 1, 1);
		Node node3 = new Node("3", 1, 1);
		Node node4 = new Node("4", 1, 1);
		
		Edge edge1 = new Edge("1", node1, node2, 1, 1, 1, 1);
		Edge edge2 = new Edge("2", node2, node3, 1, 1, 1, 1);
		Edge edge3 = new Edge("3", node2, node4, 1, 1, 1, 1);
		Edge edge4 = new Edge("4", node1, node3, 1, 1, 1, 1);
		Edge edge5 = new Edge("5", node1, node4, 1, 1, 1, 1);
		
		Graph graph = new Graph();
		graph.add(edge1);
		graph.add(edge2);
		graph.add(edge3);
		graph.add(edge4);
		graph.add(edge5);
		
//		CompactAlgo gen = new CompactAlgo();
//		Collection<Tree> set = gen.enumerateAllSpanningTree(graph);
//		Iterator iter = set.iterator();
//		while ( iter.hasNext() )
//			System.out.println(iter.next().toString()+"\n");
	}
	
	public void testCase_2()
	{
		Node node1 = new Node("1", 1, 1);
		Node node2 = new Node("2", 1, 1);
		Node node3 = new Node("3", 1, 1);
		Node node4 = new Node("4", 1, 1);
		
		Edge edge1 = new Edge("1", node1, node2, 1, 1, 1, 1);
		Edge edge2 = new Edge("2", node2, node3, 1, 1, 1, 1);
		Edge edge3 = new Edge("3", node3, node4, 1, 1, 1, 1);
		Edge edge4 = new Edge("4", node4, node1, 1, 1, 1, 1);
		Edge edge5 = new Edge("5", node4, node2, 1, 1, 1, 1);
		Edge edge6 = new Edge("6", node3, node1, 1, 1, 1, 1);
		
		Graph graph = new Graph();
		graph.add(edge1);
		graph.add(edge2);
		graph.add(edge3);
		graph.add(edge4);
		graph.add(edge5);
		graph.add(edge6);
		
//		CompactAlgo gen = new CompactAlgo();
//		Collection<Tree> set = gen.enumerateAllSpanningTree(graph);
//		Iterator iter = set.iterator();
//		while ( iter.hasNext() )
//			System.out.println(iter.next().toString()+"\n");
	}
	
	public void testCase_3()
	{
		Node node1 = new Node("1", 1, 1);
		Node node2 = new Node("2", 1, 1);
		Node node3 = new Node("3", 1, 1);
		Node node4 = new Node("4", 1, 1);
		Node node5 = new Node("5", 1, 1);
		Node node6 = new Node("6", 1, 1);
		
		Edge edge1 = new Edge("1", node1, node2, 1, 1, 1, 1);
		Edge edge2 = new Edge("2", node2, node3, 1, 1, 1, 1);
		Edge edge3 = new Edge("3", node3, node4, 1, 1, 1, 1);
		Edge edge4 = new Edge("4", node4, node5, 1, 1, 1, 1);
		Edge edge5 = new Edge("5", node5, node6, 1, 1, 1, 1);
		Edge edge6 = new Edge("6", node6, node2, 1, 1, 1, 1);
		Edge edge7 = new Edge("7", node3, node6, 1, 1, 1, 1);
		Edge edge8 = new Edge("8", node5, node3, 1, 1, 1, 1);
		Edge edge9 = new Edge("9", node4, node1, 1, 1, 1, 1);
		
		Graph graph = new Graph();
		graph.add(edge1);
		graph.add(edge2);
		graph.add(edge3);
		graph.add(edge4);
		graph.add(edge5);
		graph.add(edge6);
		graph.add(edge7);
		graph.add(edge8);
		graph.add(edge9);
		
//		CompactAlgo gen = new CompactAlgo();
//		Collection<Tree> set = gen.enumerateAllSpanningTree(graph);
//		Iterator iter = set.iterator();
//		while ( iter.hasNext() )
//			System.out.println(iter.next().toString()+"\n");
	}
	
	public void testStress()
	{
		int N = 10;
		int E = N * (N-1) / 2;
		
		Graph graph = new Graph();
		
		Node[] nodes = new Node[N];
		for(int i=1; i<=nodes.length; i++)
			nodes[i-1] = new Node(""+i, 1, 1);

		Edge[] edges = new Edge[E];
		int index = 0;
		while ( index < edges.length ) {
			for (int i=0; i<nodes.length; i++) {
				for (int j=i+1; j<nodes.length; j++) {
					edges[index] = new Edge(""+(index+1), nodes[i], nodes[j], 1, 1, 1, 1);
					graph.add(edges[index]);
					index ++;
				}
			}
		}
		
		CompactAlgo gen = new CompactAlgo();
		Collection<Graph> set = gen.generateAllSpanningGraph(graph);
//		Iterator iter = set.iterator();
//		while ( iter.hasNext() )
//			System.out.println(iter.next().toString()+"\n");
	}

}
